class Solution(object):
    def permute(self, nums):
        i = 0
        if len(nums) == 1:
            return [nums]
        res = []
        i = 0
        while i < len(nums):
            cur_name = nums[i]
            other_permute = self.permute(nums[:i] + nums[i+1:])
            for p in other_permute:
                res.append([cur_name] + p)
            #跳过重复的数字
            while i < len(nums) - 1 and nums[i + 1] == nums[i]:
                i = i + 1
            i = i + 1
        return res

    def permuteUnique(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums_sorted = sorted(nums)
        return self.permute(nums_sorted)
